﻿/* 
 * ALL code in this file were distributed under Microsoft Public License (Ms-PL).
 * http://www.microsoft.com/en-us/openness/licenses.aspx#MPL
 * Thanks to https://github.com/ricmrodrigues/autosprite
 * 
 */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace ImgCore.Sprite.Utility
{
    static class Algorithm
    {
        /// <summary>
        /// Greedy algorithm.
        /// </summary>
        /// <param name="_modules">List of modules that represent the images that need to be inserted into the sprite.</param>
        /// <returns>Near optimal placement.</returns>
        public static Placement Greedy(List<Module> _modules)
        {
            //Empty O-Tree code.
            OTree oTree = new OTree();
            OT finalOT = null;
            //Empty list of modules.
            List<Module> moduleList = new List<Module>();

            //For each module which needs to be inserted.
            foreach (Module module in _modules)
            {
                OTree bestOTree = null;
                //Add module to the list of already packed modules.
                moduleList.Add(module);
                //Set the minimum perimeter of the placement to high.
                int minPerimeter = Int32.MaxValue;

                //Try all insertation point.
                foreach (int insertationPoint in oTree.InsertationPoints())
                {
                    OTree ot = oTree.Copy();
                    ot.Insert(module.Name, insertationPoint);
                    OT oT = new OT(ot, moduleList);
                    Placement pm = oT.Placement;

                    //Choose the one with the minimum perimeter.
                    if (pm.Perimeter < minPerimeter)
                    {
                        finalOT = oT;
                        bestOTree = ot;
                        minPerimeter = pm.Perimeter;
                    }
                }
                oTree = bestOTree;
            }

            return finalOT.Placement;
        }
    }

    #region Algorithm internals

    public class Module
    {
        private int name;
        private int width;
        private int height;
        private int whiteSpace;
        private int xCoordinate;
        private int yCoordinate;
        private Image image;

        /// <summary>
        /// Module class representing an image and it's size including white space around the image.
        /// </summary>
        /// <param name="_name"></param>
        /// <param name="_image"></param>
        /// <param name="_whiteSpace">Width of white space around the image.</param>
        public Module(int _name, Image _image, int _whiteSpace)
        {
            name = _name;

            if (_image != null)
            {
                width = _image.Width + _whiteSpace;
                height = _image.Height + _whiteSpace;
            }
            //Empty module
            else
                width = height = 0;

            whiteSpace = _whiteSpace;
            xCoordinate = 0;
            yCoordinate = 0;
            image = _image;
        }

        /// <summary>
        /// Gets the width of the module.
        /// </summary>
        public int Width
        {
            get { return width; }
        }

        /// <summary>
        /// Gets the height of the module.
        /// </summary>
        public int Height
        {
            get { return height; }
        }

        /// <summary>
        /// Gets or sets the x-coordinate of the module's bottom left corner.
        /// </summary>
        public int X
        {
            get { return xCoordinate; }
            set { xCoordinate = value; }
        }

        /// <summary>
        /// Gets or sets the y-coordinate of the module's bottom left corner.
        /// </summary>
        public int Y
        {
            get { return yCoordinate; }
            set { yCoordinate = value; }
        }

        /// <summary>
        /// Gets the name of the module.
        /// </summary>
        public int Name
        {
            get { return name; }
        }

        /// <summary>
        /// Sets coordinates of module to zero.
        /// </summary>
        public void ClearCoordinates()
        {
            xCoordinate = 0;
            yCoordinate = 0;
        }

        /// <summary>
        /// Deep copy.
        /// </summary>
        /// <returns></returns>
        public Module Copy()
        {
            Module copy = new Module(name, image, whiteSpace);
            copy.xCoordinate = xCoordinate;
            copy.yCoordinate = yCoordinate;
            return copy;
        }

        /// <summary>
        /// Draws the module into a graphics object.
        /// </summary>
        /// <param name="graphics"></param>
        /// <param name="marginWidth">Margin width around the sprite.</param>
        public void Draw(Graphics graphics, int marginWidth)
        {
            graphics.DrawImage(image, xCoordinate + marginWidth, yCoordinate + marginWidth,
                image.Width, image.Height);
        }
    }
    
    class OT
    {
        private OTree oTree;
        private Dictionary<int, Module> modules;
        private Placement placement;

        /// <summary>
        /// Algoritms class for O-Tree representation.
        /// </summary>
        /// <param name="ot">The O-tree code which describes the placement.</param>
        /// <param name="_modules">Modules to be packed.</param>
        public OT(OTree ot, List<Module> _modules)
        {
            oTree = ot;
            modules = _modules.ToDictionary(item => item.Name, item => item);
            placement = null;
        }

        /// <summary>
        /// Gets the calculated placement.
        /// </summary>
        public Placement Placement
        {
            get
            {
                ToCompact();
                return placement;
            }
        }

        /// <summary>
        /// Operation of horizontal O-tree. Calculates coordinates and takes one compaction step.
        /// </summary>
        /// <returns>Vertical constraint graph</returns>
        private Graph ToVerticalConstraintGraph()
        {
            //Empty module representing the root of the tree
            Module root = new Module(-1, null, 0);
            modules.Add(-1, root);
            oTree.ModuleSequence.Insert(0, -1);

            //Stack containing module labels for parent module calculation
            Stack<int> stack = new Stack<int>();
            stack.Push(-1);

            //Vertical contsraint graph
            Graph constraintGraph = new Graph(oTree.ModuleSequence);

            //Actual parent and child module
            Module parent = root;
            Module child;

            //Horizontal contour for quick y-coordinate calculation
            Contour contour = new HorizontalContour(root);

            //Index of child module in ModuleSequence
            int childIndex = 0;

            foreach (Bit bit in oTree.DfsSequence)
            {
                //Forth step in DFS traversing, coordinates need to be calcuted
                if (bit == 0)
                {
                    child = modules[oTree.ModuleSequence[++childIndex]];

                    //In horizontal O-tree, child module is on the rigth side of the parent module and adjacent with it
                    child.X = parent.X + parent.Width;
                    //Finding the minimum y-coordinate
                    child.Y = contour.FindMax(child.X + child.Width);

                    //There is an egde in the vertical constraint graph, where the minimum is found
                    constraintGraph.AddEdge(contour.WhereMax.Name, child.Name, child.X);

                    //Updating contour
                    contour.Update(child);

                    //Now child module is the actual parent
                    parent = child;
                    stack.Push(parent.Name);
                }

                //Back step in DFS traversing
                else
                {
                    //Updating parent module and the insertation index of the contour
                    stack.Pop();
                    parent = modules[stack.Peek()];
                    contour.InsertationIndex = contour.ModuleSequence.IndexOf(parent);
                }

            }

            //Removing root module
            modules.Remove(-1);
            oTree.ModuleSequence.RemoveAt(0);

            return constraintGraph;
        }

        /// <summary>
        /// Operation of vertical O-tree. Calculates coordinates and takes one compaction step.
        /// </summary>
        /// <returns>Horizontal constraint graph</returns>
        private Graph ToHorizontalConstraintGraph()
        {
            //Empty module representing the root of the tree
            Module root = new Module(-1, null, 0);
            modules.Add(-1, root);
            oTree.ModuleSequence.Insert(0, -1);

            //Stack containing module labels for parent module calculation
            Stack<int> stack = new Stack<int>();
            stack.Push(-1);

            //Vertical contsraint graph
            Graph constraintGraph = new Graph(oTree.ModuleSequence);

            //Actual parent and child module
            Module parent = root;
            Module child;

            //Vertical contour for quick x-coordinate calculation
            Contour contour = new VerticalContour(root);

            //Index of child module in ModuleSequence
            int childIndex = 0;

            foreach (Bit bit in oTree.DfsSequence)
            {
                //Forth step in DFS traversing, coordinates need to be calcuted
                if (bit == 0)
                {
                    child = modules[oTree.ModuleSequence[++childIndex]];

                    //In vertical O-tree, child module is on the top of parent module and adjacent with it
                    child.Y = parent.Y + parent.Height;
                    //Finding the minimum x-coordinate
                    child.X = contour.FindMax(child.Y + child.Height);

                    //There is an egde in the horizontal constraint graph, where the minimum is found
                    constraintGraph.AddEdge(contour.WhereMax.Name, child.Name, child.Y);

                    //Updating contour
                    contour.Update(child);

                    //Now child module is the actual parent
                    parent = child;
                    stack.Push(parent.Name);
                }

                //Back step in DFS traversing
                else
                {
                    //Updating parent module and insertation index of the contour
                    stack.Pop();
                    parent = modules[stack.Peek()];
                    contour.InsertationIndex = contour.ModuleSequence.IndexOf(parent);
                }

            }

            //Removing root module
            modules.Remove(-1);
            oTree.ModuleSequence.RemoveAt(0);
            return constraintGraph;
        }

        /// <summary>
        /// Creates LB-compact placement with sequence of compaction steps.
        /// </summary>
        private void ToCompact()
        {
            //Stop condition of while loop, true if compaction steps change the O-tree
            bool changed = true;

            //Copy of components of the actual O-tree. If compaction steps does not change them, placement is compact.
            List<Bit> DfsSequenceCopy = new List<Bit>(oTree.DfsSequence);
            List<int> moduleSequenceCopy = new List<int>(oTree.ModuleSequence);

            while (changed)
            {
                changed = false;

                //Vertical constraint graph from horizontal O-tree.
                Graph gVertical = ToVerticalConstraintGraph();
                //Vertical O-tree from vertical constraint graph.
                oTree.ModuleSequence = gVertical.DepthFirstSearch(oTree.DfsSequence);

                //Horizontal constraint graph from vertical O-tree.
                Graph gHorizontal = ToHorizontalConstraintGraph();
                //Horizontal O-tree from horizontal constraint graph.
                oTree.ModuleSequence = gHorizontal.DepthFirstSearch(oTree.DfsSequence);

                //Checking the changes of the O-Tree after compaction steps.
                //If the O-tree has changed, more compaction steps could be needed on the changed tree.
                if (!(oTree.DfsSequence.SequenceEqual(DfsSequenceCopy) &&
                      oTree.ModuleSequence.SequenceEqual(moduleSequenceCopy)))
                {
                    moduleSequenceCopy = new List<int>(oTree.ModuleSequence);
                    DfsSequenceCopy = new List<Bit>(oTree.DfsSequence);
                    changed = true;
                }
            }

            //Compact placement.
            placement = new Placement(modules.Values.ToList<Module>());
        }
    }

    //Code class for O-Tree representation. O-Tree encodes a placement by a sequence of 
    //module labels and a 0-1 sequence describing the tree structure.
    class OTree
    {
        private List<int> moduleSequence;
        private List<Bit> dfsSequence;

        /// <summary>
        /// Creates new instance of O-Tree code with empty sequences.
        /// </summary>
        public OTree()
        {
            moduleSequence = new List<int>();
            dfsSequence = new List<Bit>();
        }

        /// <summary>
        /// Gets or sets the sequence of module labels.
        /// </summary>
        public List<int> ModuleSequence
        {
            get { return moduleSequence; }
            set { moduleSequence = value; }
        }

        /// <summary>
        /// Gets or sets the 0-1 sequence of DFS-order.
        /// </summary>
        public List<Bit> DfsSequence
        {
            get { return dfsSequence; }
        }

        /// <summary>
        /// Deep copy.
        /// </summary>
        /// <returns></returns>
        public OTree Copy()
        {
            OTree ot = new OTree();
            ot.moduleSequence = new List<int>(moduleSequence);
            ot.dfsSequence = new List<Bit>(dfsSequence);

            return ot;
        }

        /// <summary>
        /// Calculates insertation positions according to DFS-sequence.
        /// </summary>
        /// <returns>IEnumerable collection of zero based indices in DFS-sequence where new element 
        /// can be inserted.</returns>
        public IEnumerable<int> InsertationPoints()
        {
            for (int i = 0; i <= dfsSequence.Count; i++)
                yield return i;
        }

        /// <summary>
        /// Inserts new element into O-Tree code.
        /// </summary>
        /// <param name="item">Module label.</param>
        /// <param name="dfsIndex">DFS-sequence index.</param>
        public void Insert(int item, int dfsIndex)
        {
            //Inserting 0 and 1 into DFS sequence representing a forth and a back step.
            dfsSequence.InsertRange(dfsIndex, new Bit[] { 0, 1 });

            //Calculating index of module label in moduleSequence.
            //Every forth step in DFS traversing before dfsIndex belong to a previous module in moduleSequence.
            int moduleIndex = dfsSequence.GetRange(0, dfsIndex).Count(b => b == 0);
            moduleSequence.Insert(moduleIndex, item);
        }
    }

    //Bit struct. In reference, DFS-order is stored in a 0-1 sequence, 
    //this struct has been created to follow terminology.
    struct Bit
    {
        private bool bit;

        private Bit(int n)
        {
            this.bit = (n == 1) ? true : false;
        }

        public static implicit operator Bit(int n)
        {
            return new Bit(n);
        }

        public override bool Equals(object obj)
        {
            if (obj is Bit)
                return this == ((Bit)obj);
            else if (obj is int)
                return this == (int)obj;

            return false;
        }

        public override int GetHashCode()
        {
            return bit.GetHashCode();
        }

        public static bool operator ==(Bit b, int n)
        {
            if ((b.bit == true && n == 1) || (b.bit == false && n == 0))
                return true;
            else return false;
        }

        public static bool operator !=(Bit b, int n)
        {
            if (!((b.bit == true && n == 1) || (b.bit == false && n == 0)))
                return true;
            else return false;
        }

        public static bool operator ==(Bit b1, Bit b2)
        {
            if ((b1.bit == true && b2.bit == true) || (b1.bit == false && b2.bit == false))
                return true;
            else return false;
        }

        public static bool operator !=(Bit b1, Bit b2)
        {
            if (!((b1.bit == true && b2.bit == true) || (b1.bit == false && b2.bit == false)))
                return true;
            else return false;
        }
    }

    //Contour is the list of the modules on the top (horizontal contour) or on the right (vertical contour) of the 
    //placement. It is needed for linear time computation of the modules coordinates. It is easier to understand 
    //it from some figure. See reference.
    abstract class Contour
    {
        protected List<Module> moduleSequence;
        protected int insertationIndex;
        protected Module whereMax;

        protected void Construct(Module root)
        {
            moduleSequence = new List<Module>();
            moduleSequence.Add(root);
            whereMax = root;
            insertationIndex = -1;
        }

        /// <summary>
        /// Sets the insertation index of the contour.
        /// </summary>
        public int InsertationIndex
        {
            set { insertationIndex = value; }
        }

        /// <summary>
        /// Gets the sequence of modules whereof the contour consists.
        /// </summary>
        public List<Module> ModuleSequence
        {
            get { return moduleSequence; }
        }

        /// <summary>
        /// Gets the module with the maximum y-coordinate in a given x-coordinate range or conversely.
        /// It is calculated by FindMax method.
        /// </summary>
        public Module WhereMax
        {
            get { return whereMax; }
        }

        public abstract int FindMax(int to);

        /// <summary>
        /// Inserts new module into the contour and clears WhereMax value.
        /// </summary>
        /// <param name="module"></param>
        public void Update(Module module)
        {
            moduleSequence.Insert(++insertationIndex, module);
            whereMax = new Module(-1, null, 0);
        }
    }

    class HorizontalContour : Contour
    {
        /// <summary>
        /// Contour class for quick computation of y-coordinates during working with horizontal O-Tree.
        /// </summary>
        /// <param name="root">First element of the contour.</param>
        public HorizontalContour(Module root)
        {
            Construct(root);
        }

        /// <summary>
        /// Finds the minimum y-coordinate where the module can be inserted.
        /// </summary>
        /// <param name="to">Maximum x-coordinate until modules below the actual module need to be checked.</param>
        /// <returns></returns>
        public override int FindMax(int to)
        {
            int max = 0;
            //Actual module does not need to be checked.
            int indexFrom = insertationIndex + 1;

            //Checking modules in contour.
            while (indexFrom < moduleSequence.Count && moduleSequence[indexFrom].X < to)
            {
                //Overwriting maximum.
                if (max < moduleSequence[indexFrom].Y + moduleSequence[indexFrom].Height)
                {
                    max = moduleSequence[indexFrom].Y + moduleSequence[indexFrom].Height;
                    whereMax = moduleSequence[indexFrom];
                }

                //Removing modules, which are covered by the module will be isnserted.
                if (moduleSequence[indexFrom].X + moduleSequence[indexFrom].Width <= to)
                {
                    moduleSequence.RemoveAt(indexFrom);
                }

                else
                    indexFrom++;
            }

            return max;
        }
    }

    class VerticalContour : Contour
    {
        /// <summary>
        /// Contour class for quick computation of x-coordinates during working with vertical O-Tree.
        /// </summary>
        /// <param name="root">First element of the contour.</param>
        public VerticalContour(Module root)
        {
            Construct(root);
        }

        /// <summary>
        /// Finds the minimum x-coordinate where the module can be inserted.
        /// </summary>
        /// <param name="to">Maximum y-coordinate until modules on the left of the actual module need to be checked.</param>
        /// <returns></returns>
        public override int FindMax(int to)
        {
            int max = 0;
            //Actual module does not need to be checked.
            int indexFrom = insertationIndex + 1;

            //Checking modules in contour.
            while (indexFrom < moduleSequence.Count && moduleSequence[indexFrom].Y < to)
            {
                //Overwriting maximum.
                if (max < moduleSequence[indexFrom].X + moduleSequence[indexFrom].Width)
                {
                    max = moduleSequence[indexFrom].X + moduleSequence[indexFrom].Width;
                    whereMax = moduleSequence[indexFrom];
                }

                //Removing modules, which are covered by the module will be inserted.
                if (moduleSequence[indexFrom].Y + moduleSequence[indexFrom].Height <= to)
                {
                    moduleSequence.RemoveAt(indexFrom);
                }

                else
                    indexFrom++;
            }

            return max;
        }
    }

    class Graph
    {
        protected Dictionary<int, GraphNode> nodes;

        /// <summary>
        /// Directed graph with weigted edges.
        /// </summary>
        /// <param name="_nodes">List of node labels.</param>
        public Graph(List<int> _nodes)
        {
            //Nodes of the graph.
            nodes = new Dictionary<int, GraphNode>();

            //Initializing list of edges for all nodes.
            foreach (int node in _nodes)
            {
                GraphNode gn = new GraphNode();
                gn.InitializeEdges();
                nodes.Add(node, gn);
            }
        }

        /// <summary>
        /// Adds edge to the graph.
        /// </summary>
        /// <param name="from">Source node of the edge.</param>
        /// <param name="to">Sink node of the edge.</param>
        /// <param name="weight">Weight of the edge.</param>
        public void AddEdge(int from, int to, int weight)
        {
            nodes[from].outgoingEdges.Add(to, weight);
            nodes[to].incomingEdges.Add(from, weight);
        }

        /// <summary>
        /// Ordered visit, neighbors with lower weight have higher preference. If the graph is horizontal, weight 
        /// means x-coordinate of the module, which is represented by the sink node of the edge. If the graph is 
        /// vetrical, weight means the y-coordinate.
        /// </summary>
        /// <param name="node">Actual node.</param>
        /// <param name="visitedNodes">Visited nodes.</param>
        /// <param name="topologicalOrder">Topological order of the graph.</param>
        /// <param name="DFSSequence">0-1 sequence representing of the DFS traversing. 0 means forth step,
        /// 1 means back step.</param>
        private void VisitNode(int node, Dictionary<int, bool> visitedNodes, List<int> topologicalOrder, List<Bit> DFSSequence)
        {
            //If node is not visited yet
            if (!visitedNodes[node])
            {
                visitedNodes[node] = true;

                //Adding node to topological order and adding a 0 to DFS sequense strores the forth step belongs 
                //to the module
                topologicalOrder.Add(node);
                DFSSequence.Add(0);

                //Ordering neighbors by their weights
                var orderedNeighbors = from neighbor in nodes[node].outgoingEdges.Keys
                                       orderby nodes[node].outgoingEdges[neighbor]
                                       select neighbor;

                //Ordered list of neighbors
                List<int> neighborsOfNode = new List<int>(orderedNeighbors);

                //Visiting nodes in the afore calculated order.
                foreach (int neighbor in neighborsOfNode)
                {
                    VisitNode(neighbor, visitedNodes, topologicalOrder, DFSSequence);
                }
            }

            //If node and all of its DFS descendants are visited, it's needed to store the back step 
            //belonging to the module.
            DFSSequence.Add(1);
        }

        /// <summary>
        /// Ordered depth first search. Calculates module sequence and DFS sequence belonging to the graph. 
        /// These determines the O-Tree with the same orientation what the graph has.
        /// </summary>
        /// <param name="DFSSequence">O-Tree DFSSequence.</param>
        /// <returns>O-Tree ModuleSequence.</returns>
        public List<int> DepthFirstSearch(List<Bit> DFSSequence)
        {
            //Clearing DFS sequence and creating an empty list of module labels.
            DFSSequence.Clear();
            List<int> nodeOrder = new List<int>();
            //Every node is unvisited yet.
            Dictionary<int, bool> visitedNodes = nodes.Keys.ToDictionary(item => item, item => false);

            //Visit starts at root module representing by label -1.
            VisitNode(-1, visitedNodes, nodeOrder, DFSSequence);

            //Removing root module.
            nodeOrder.RemoveAt(0);
            DFSSequence.RemoveAt(0);
            DFSSequence.RemoveAt(DFSSequence.Count - 1);

            return nodeOrder;
        }
    }

    class GraphNode
    {
        public Dictionary<int, int> incomingEdges;
        public Dictionary<int, int> outgoingEdges;

        public void InitializeEdges()
        {
            incomingEdges = new Dictionary<int, int>();
            outgoingEdges = new Dictionary<int, int>();
        }
    }
    
    #endregion
}
